/**
 * 线性数据结构 - 数组, 动态数组, 优点: 随机访问
 *  > 连续型物理结构
 *  > 动态扩缩容能力
 * @param <E> 泛型参数
 */
public class Array<E> {

    private E[] data;
    private int size;

    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array() { this(10); }

    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
    public int capacity() { return data.length; }

    // 添加
    public void addFirst(E elem) { add(0, elem); }
    public void add(int index, E elem) {
        if (index < 0 || index > size) throw new IllegalArgumentException("add failed, index out of range");
        // if (size == data.length) throw new IllegalArgumentException("add failed, Array is full");
        // 扩容动作
        if (size == data.length) { ensureCapacity( data.length * 2); }

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];
        data[index] = elem;
        size++;
    }
    public void addLast(E elem) { add(size, elem); }

    // 查找
    public E getFirst() { return get(0); }
    public E get(int index) {
        if (index < 0 || index >= size) throw new IllegalArgumentException("get failed, index out of range");
        return data[index];
    }
    public E getLast() { return get(size-1); }

    // 修改
    public E set(int index, E elem) {
        if (index < 0 || index >= size) throw new IllegalArgumentException("set failed, index out of range");
        E old = data[index];
        data[index] = elem;
        return old;
    }

    // 搜索
    public int find(E elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) return i;
        }
        return -1;
    }

    // 判断
    public boolean contains(E elem) { return find(elem) != -1; }

    // 删除
    public E removeFirst() { return remove(0); }
    public E remove(int index) {
        if (index < 0 || index >= size) throw new IllegalArgumentException("remove failed, index out of range");
        E old = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;

        // 缩容动作 ( 算法设计中 lazy 思想， 有效避免复杂度震荡的问题， 参考线段树的处理 )
        // 缩容动作到一定程度就不需要再进行， 不能缩小到0
        if (size == (data.length / 4) && (data.length / 2 != 0)) { ensureCapacity(data.length / 2);}
        return old;
    }
    public E removeLast() { return remove(size - 1); }

    // 删除指定元素
    public void removeElem(E elem) {
        int index = find(elem);
        if (index != -1) remove(index);
    }

    // 删除指定的所有元素, 返回删除元素个数
    public int removeAllElem(E elem) {
        int cnt = 0;
        int index = -1;
        while ((index = find(elem)) != -1) {
            remove(index);
            cnt++;
        }

        return cnt;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array(size=%d, capacity=%d):\n", size, data.length));
        res.append(" > [");
        for (int i = 0; i < size; i++) {
            res.append(get(i));
            if (i != size - 1) res.append(", ");
        }
        res.append("]");
        return res.toString();
    }

    public void ensureCapacity(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) newData[i] = data[i]; 
        data = newData; 
    }


}
 